package com.util;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

import com.common.model.TreeNode;

/**
 * 常用的树操作工具类
 *
 * @author think
 * @date 2020/10/30
 */
public class TreeOperUtil {
    /**
     * 创建结点
     *
     * @param datas datas
     * @param index index
     * @param <T>   T
     * @return T
     */
    public static <T> TreeNode<T> createTree(T[] datas, int index) {
        TreeNode<T> parent = null;
        if (index >= datas.length) {
            return parent;
        }
        if (Objects.nonNull(datas[index])) {
            parent = new TreeNode<>(datas[index]);
            parent.setLeftChild(createTree(datas, 2 * index + 1));
            if (Objects.nonNull(parent.getLeftChild())) {
                parent.getLeftChild().setParent(parent);
            }
            parent.setRightChild(createTree(datas, 2 * index + 2));
            if (Objects.nonNull(parent.getRightChild())) {
                parent.getRightChild().setParent(parent);
            }
        }
        return parent;
    }

    public static <T> List<T> preScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        Stack<TreeNode<T>> stack = new Stack<>();
        for (TreeNode<T> node = root; !stack.isEmpty() || Objects.nonNull(node);) {
            if (Objects.isNull(node)) {
                node = stack.pop();
            }
            result.add(node.getValue());
            if (Objects.nonNull(node.getRightChild())) {
                stack.push(node.getRightChild());
            }
            node = node.getLeftChild();
        }
        return result;
    }

    public static <T> List<T> inScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        Stack<TreeNode<T>> stack = new Stack<>();
        for (TreeNode<T> node = root; !stack.isEmpty() || Objects.nonNull(node);) {
            while (Objects.nonNull(node)) {
                stack.push(node);
                node = node.getLeftChild();
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                result.add(node.getValue());
                node = node.getRightChild();
            }
        }
        return result;
    }

    public static <T> List<T> postScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        Stack<TreeNode<T>> stack = new Stack<>();
        for (TreeNode<T> node = root; !stack.isEmpty() || Objects.nonNull(node);) {
            while (Objects.nonNull(node)) {
                stack.push(node);
                node = node.getLeftChild();
            }
            while (!stack.isEmpty() && node == stack.peek().getRightChild()) {
                node = stack.pop();
                result.add(node.getValue());
            }
            if (stack.isEmpty()) {
                break;
            } else {
                node = stack.peek().getRightChild();
            }
        }
        return result;
    }

    public static <T> List<T> preRecScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        if (Objects.nonNull(root)) {
            result.add(root.getValue());
            result.addAll(preRecScan(root.getLeftChild()));
            result.addAll(preRecScan(root.getRightChild()));
        }
        return result;
    }

    public static <T> List<T> inRecScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        if (Objects.nonNull(root)) {
            preRecScan(root.getLeftChild());
            result.add(root.getValue());
            preRecScan(root.getRightChild());
        }
        return result;
    }

    public static <T> List<T> postRecScan(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        if (Objects.nonNull(root)) {
            preRecScan(root.getLeftChild());
            preRecScan(root.getRightChild());
            result.add(root.getValue());
        }
        return result;
    }

    /**
     * 建二叉搜索树
     * 
     * @param <T>   类型
     * @param list  列表
     * @param left  左边界
     * @param right 右边界
     * @return 二叉搜索树根节点
     */
    public static <T> TreeNode<T> createBstTree(List<T> list, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode<T> root = new TreeNode<T>(list.get(mid));
        root.setLeftChild(createBstTree(list, left, mid - 1));
        root.setRightChild(createBstTree(list, mid + 1, right));
        return root;
    }

    public static <T> ArrayList<ArrayList<T>> levelOrder(TreeNode<T> root){
        ArrayList<ArrayList<T>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode<T>> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<T> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode<T> node = queue.poll();
                if (Objects.nonNull(node)) {
                    level.add(node.getValue());
                    if (node.getLeftChild() != null) {
                        queue.offer(node.getLeftChild());
                    }
                    if (node.getRightChild() != null) {
                        queue.offer(node.getRightChild());
                    }
                }
            }
            result.add(level);
        }
        System.out.println(result);
        return result;
    }
    
    public static <T> int maxHight(TreeNode<T> root) {
        if (Objects.isNull(root)) {
            return 0;
        }
        return Math.max(1 + maxHight(root.getLeftChild()), 1 + maxHight(root.getRightChild()));
    }

    public static <T> int minHight(TreeNode<T> root) {
        if (Objects.isNull(root)) {
            return 0;
        }
        if (Objects.isNull(root.getLeftChild()) || Objects.isNull(root.getRightChild())) {
            return 1;
        }
        return 1 + Math.min(minHight(root.getLeftChild()), minHight(root.getRightChild()));
    }

    public static <T> boolean isBalanced(TreeNode<T> root) {
        if (Objects.isNull(root)) {
            return true;
        }
        return Math.abs(maxHight(root.getLeftChild()) - maxHight(root.getRightChild())) <= 1
                && isBalanced(root.getLeftChild()) && isBalanced(root.getRightChild());
    }
    
    /**
     * 是否是镜像对称
     *
     * @param root 根结点
     * @return 状态
     */
    public static <T> boolean isSymmetric(TreeNode<T> root){
        /* 思路：首先根结点以及其左右子树，左子树的左子树和右子树的右子树相同，
         * 左子树的右子树，和右子树的左子树相同。我们采用递归的方式 */
        if (root == null) {
            return false;
        }
        return comRoot(root.getLeftChild(),root.getRightChild());
    }
    
    private static <T> boolean comRoot(TreeNode<T> left,TreeNode<T> right){
        if (left == null) {
            return right == null;
        }
        // 能执行到这一步，说明他的左子树肯定是不为空，此时比较右子树如果为空，那么肯定返回false
        if (right == null) {
            return false;
        }
        if (!left.getValue().equals(right.getValue())) {
            return false;
        }
        // 能执行到这一步，说明其传进来的左子树和右子树不为null，且对应值相等，此时我们只需要，进行递归比较
        // 传进来的左子树的左子树和传进来右子树的右子树。传进来的左子树的右子树和传进来的右子树的左子树。
        return comRoot(left.getLeftChild(),right.getRightChild()) && comRoot(left.getRightChild(),right.getLeftChild());
    }
    
    /**
     * 二叉树的路径总和等于预设值
     *
     * @param root 根结点
     * @param sum 总和
     * @return 状态
     */
    public static <T> boolean hasPathSum(TreeNode<T> root,int sum){
        boolean lans, rans;
        if (root == null) {
            return false;
        } else if (root.getValue().equals(sum) && root.getLeftChild() == null && root.getRightChild() == null) {
            // 在递归里，直接得到最终目标或者永远不能得到最终目标的先做判断（即，寻找退出条件）
            return true;
        } else {
            lans = Objects.nonNull(root.getLeftChild()) && hasPathSum(root.getLeftChild(),sum - Integer.parseInt(String.valueOf(root.getValue())));
            rans = Objects.nonNull(root.getRightChild()) && hasPathSum(root.getRightChild(),sum - Integer.parseInt(String.valueOf(root.getValue())));
            // 不能return (root.left!=null)?hasPathSum(root.left ,
            // sum-root.val):false||(root.right!=null)?hasPathSum(root.right , sum-root.val):false;
            return lans || rans;
            // 左右两条路径有至少一条走通即可，两边要同时判断(放在一句里，同时执行)
        }
    }
    
    public static <T> int maxVal(TreeNode<T> node){
        if (Objects.isNull(node)) {
            return -1;
        }
        int left = maxVal(node.getLeftChild());
        int right = maxVal(node.getRightChild());
        T root = node.getValue();
        return Math.max(Integer.parseInt(String.valueOf(root)),Math.max(left,right));
    }
}
